Masala #0453

Isfandiyor Liplandiya davlatiga asos soldi. Liplandiya \(n\) ta shahar va ular orasida \(n-1\) ta yo’l bor (Liplandiyani daraxt – oddiy, bog’lamli va sikllarsiz graf deyishimiz mumkin).

Isfandiyor Liplandiyaning poytaxtini \(1\) – shahar deb nomladi. So’ngra u \(1\)-shahardan eng yaqin hali raqamlanmagan (agar eng yaqinlari bir nechta bo’lsa ixtiyoriysiga bordi) shaharga bordi va o’sha shaharni \(2\)-shahar deb nomladi. So’ngra \(2\)-shaharga eng yaqin hali raqamlanmagan shaharga borib uni \(3\)-shahar deb nomladi. Shu tartibda shaharlarga \(1...n\) sonlar bilan raqamlab chiqdi.

\(dist(a,b)\) deb \(a\) shahardan \(b\) shaharga boruvchi eng qisqa yo’lning uzunligini ataymiz. Sizga \(q\) ta so’rovda \(x\) soni beriladi. Sizning vazifangiz \(dist(a,b) \geq x\) bo’lgan leksikografik eng kichik \((a,b)\) juftlikni topish.

Birinchi qatorda \(n\) natural son \((2 \leq n \leq 200000)\).
Keyingi \(n-1\) ta qatorda 𝑎 va 𝑏 qo’shni shaharlar raqamlari beriladi \((1 \leq a, b \leq n, a \neq b)\).
Keyingi qatorda \(q\) natural son \((1 \leq q \leq 200000)\).
Keyingi \(q\) ta qatorda \(x\) butun son \((0 \leq x < n)\).

Kiritilgan graf daraxt ekanligi va shaharlar Isfandiyor xohlaganiday raqamlangani kafolatlanadi.

Har bir so’rov uchun agarda bunday juftlik mavjud bo’lsa, leksikografik eng kichigini, aks holda ikkita \(-1\) ni chop eting.